package com.yangjiayu.algorithm.array;

import java.util.Arrays;

/*
Leetcode 31 下一个排列
 */
public class NextPermutation {

    //方法一：暴力法 ==》 求一个全排列 n! 非常恐怖 （x）

    //方法二：从后向前找到升序子序列，然后确定调整后子序列的最高位，剩余部分升序排列
    public void nextPermutation(int[] nums) {
        int n = nums.length;
//     1.从后向前找到升序子序列 找到第一次下降的数，位置为k
        int k = n-2;
        while(k >= 0 && nums[k] >= nums[k+1]){
            k--;
        }
        //找到k 就是需要调整的最高位

        //2.如果k = -1 说明所有数降序排列【特殊情况】，改成升序排列
        if( k==-1 ){
            Arrays.sort(nums);//原地排列
            return;
        }

        //3.一般情况： k>=0
        //3.1 以此遍历剩余降序排列的部分，找到要替换最高位的那个数
        int i = k + 2;
        while( i<n && nums[i] > nums[k] ){
            i++;
        }
        //当前的i 就是后面部分第一个比nums[k]小的数，i-1 就是替换的数

        //3.2 交换i-1 和 k位置上的数
        int temp = nums[k];
        nums[k] = nums[i-1];
        nums[i-1] = temp;

        //3.3 剩余部分升序排列
        Arrays.sort(nums,k+1,n);
        //也可以直接前后调换
//        int start = k + 1;
//        int end = n -1;
//        while(start < end){
//            int tmp = nums[start];
//            nums[start] = nums[end];
//            nums[end] = temp;
//            start++;
//            end--;
//        }

        return;

    }


    //O（nlogn ）方法改进，将降序数组翻转的操作提取出来
    public void nextPermutation1(int[] nums) {
        int n = nums.length;
//     1.从后向前找到升序子序列 找到第一次下降的数，位置为k
        int k = n-2;
        while(k >= 0 && nums[k] >= nums[k+1]){
            k--;
        }
        //找到k 就是需要调整的最高位

        //2.如果k = -1 说明所有数降序排列【特殊情况】，改成升序排列
        if( k==-1 ){
//            Arrays.sort(nums);//原地排列 这个特殊情况居然O（logn） 可以改进
            reverse(nums,0,n-1);
            return;
        }

        //3.一般情况： k>=0
        //3.1 以此遍历剩余降序排列的部分，找到要替换最高位的那个数
        int i = k + 2;
        while( i<n && nums[i] > nums[k] ){
            i++;
        }
        //当前的i 就是后面部分第一个比nums[k]小的数，i-1 就是替换的数

        //3.2 交换i-1 和 k位置上的数
//        int temp = nums[k];
//        nums[k] = nums[i-1];
//        nums[i-1] = temp;
        swap(nums,k,i-1);

        //3.3 剩余部分升序排列
//        Arrays.sort(nums,k+1,n);
        //也可以直接前后调换
        int start = k + 1;
        int end = n -1;
        reverse(nums,start,end);
        return;

    }

    //定义一个反转数组的方法
    public void reverse(int[] nums,int start,int end){
        while(start < end){
            swap(nums,start,end);
            start++;
            end--;
        }
    }

    //定义一个方法：交换数组当中两个元素
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }



    public static void main(String[] args) {
        int[] input = {1,2,3};
        NextPermutation nextPermutation = new NextPermutation();
        nextPermutation.nextPermutation(input);
        for (int i : input) {
            System.out.print(i+"\t");
        }
    }

}
